Many methods for capturing three-dimensional (3D) scene depth information are known. Structured light methods rely on establishing a mapping from the coordinate system of a structuring pattern projected onto the scene to the coordinate system of an image captured by a camera viewing the scene illuminated by the structuring pattern. The projected structuring pattern can be regarded as a ruler pattern useful for measuring aspects of the scene. Once this mapping is determined, knowledge of the relative geometry of the projector and camera and calibration parameters of the camera and projector can be used to determine the depth map of the scene. There are many known ways of establishing this coordinate mapping, most being founded upon the trigonometric relationship of the projector and camera. The depth map can be used for a number of purposes, including 3D modelling of an object, and the adjustment of light and other imaging parameters to provide for better capturing of images.
One known way of establishing the coordinate mapping is through the use of coded structured light. It is known to generate patterns with a “2D window” property such that a defined 2D window around any discrete location in the pattern contains a sub-pattern (a window code) that is unique to that location. Projecting such a pattern onto the scene ensures that a dense set of correspondences between the captured image and the projected image can be obtained.
Much of the work to date has used binary codes such as de Bruin arrays (also known as de Bruin Tori or Perfect Maps) or M-arrays (also known as Semi-Perfect Maps). However, though such binary codes are relatively easy to construct, they have two disadvantages. Firstly, to code each location in a discrete image having M locations, the binary map must use a window containing at least m≧log2 (M) points. For large M this will require a large window which in applications such as Coded Structured Light can mean that local errors affect a larger portion of the map. Secondly, in these patterns all or almost all possible window codes will occur exactly once, which means that the pattern is not very robust to errors in the measurement of point values which can result from noise or variation in the surface reflectivity.
By using a K-ary rather than a binary code, the window need only contain m≧2 logK (M) points, thus reducing the number of neighbourhood points required in the local window by a factor of log2 (K). Occlusion in the 3D scene can result in some parts of the projected ruler pattern not being visible from the viewpoint of the camera. Because the local window size is smaller in a K-ary code, occlusion will affect a smaller number of points around an occlusion boundary than are affected in a binary code.
Constructing patterns which only sparsely use the set of all possible window codes means that a small local window can code for many more locations than are required over the full 2D-ruler pattern. Codes can then be chosen to enforce a minimum hamming distance in the code space between codes used in the pattern. Errors in the recovered image that lead to errors in the location code can then be detected and potentially corrected.
Such patterns are described in “Structured Light Using Pseudorandom Codes”, R. A. Morano et. al., IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 3, March 1998, hereafter “Morano”. Morano referred to the patterns as “perfect submaps” since the patterns used a subset of the possible codes available in the defined window, and used each code only once. To create the patterns, Morano used a brute force search. However Morano's approach becomes computationally expensive for even moderately large arrays, limiting the resolution that can be achieved in practice. With large arrays it is also necessary to address the problem of efficiently decoding the location from the window code.
In Coded Structured Light the captured image is subject to geometric distortion because of the 3D shape of the surface on which it is projected. This can complicate the process of extracting the window code. Many existing methods rely on having isolated elements (such as coloured spots) in their patterns so that the centres of each element can be identified to deal with geometric distortion. Requiring disjoint elements in the pattern limits the spatial resolution that can be achieved. A need exists for a technique that can be efficiently decoded for non-disjoint regions of the pattern.
Variation in the surface reflectivity (due to surface colour or fine scale texture of the reflecting surface) can result in spatial variations in the captured intensity which can greatly complicate the problem of accurately recovering the code. A need exists for an approach to coding the patterns that ensures robust recovery of the coded information.